# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        pre = ListNode(0)
        pre.next = head
        length = 0
        # 计算长度
        while head:
            length += 1
            head = head.next
        length -= n
        # 复原
        head = pre
        # 找到 L-n-1个节点
        while length > 0:
            length -= 1
            head = head.next
        # 删除这个节点 ，把当前节点的指针，指向下一个节点指针
        head.next = head.next.next
        return pre.next


solution = Solution()
node = ListNode(4)
node.next = ListNode(5)
node.next = ListNode(1)
node.next = ListNode(9)
res = solution.removeNthFromEnd(node, 2)
print(res)
